求最长回文子串是面试中常考的题目，这道题有三种解法：动态规划、中心扩展法和Manacher算法。
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
1
2
3
| >输入：s = "babad"
>输出："bab"
>解释："aba" 同样是符合题意的答案。
|
一、动态规划
状态： dp[i][j]表示子串下标[i…j]均为回文子串
状态转移方程：dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1] s[i] == s[j] 的前提下，继续判断去掉头尾的子串是否为回文串
边界条件：j - 1 - (i + 1) + 1 < 2 => j - i < 3 两个以上才能构成区间
每一步的计算尽可能利用了前一步的结果，是一种空间换时间的算法思想。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| string longestPalindrome(string s) {
int n = s.size();
if(n < 2) {
return s;
}
int maxnlen = 1;
int begin = 0;
vector<vector<bool>>dp(n, vector<bool>(n, false));
for(int i = 0; i < n; i++) {
dp[i][i] = true;
}
for(int j = 1; j < n; j++) {
for(int i = 0; i < j; i++) {
if(s[i] != s[j]) {
dp[i][j] = false;
}
else {
if(j - i < 3) {
dp[i][j] = true;
}
else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if(dp[i][j] && j - i + 1 > maxnlen) {
maxnlen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxnlen);
}
|
